'''
@Company: TWL
@Author: xue jian
@Email: xuejian@kanzhun.com
@Date: 2020-04-18 23:25:43
'''
class Solution:
    def findMinFibonacciNumbers(self, k: int) -> int:
        a = 1
        if k<=2:
            return 1
        f = [1]
        b = 1
        while b<=k:
            # print(b, k)
            f.append(b)
            tmp = b
            b += a
            a = tmp
        # print(f)
        re = 0
        import math
        while k != 0:
            print(f)
            re += int(k/f[-1])
            k = int(k%f[-1])
            f.pop()
            print(k, re)
        return re
            
        
if __name__ == "__main__":
    s = Solution()
    print(s.findMinFibonacciNumbers(7))